'''
	直接插入排序
	时间复杂度：最好：O(n) 平均：O(n^2) 最坏：O(n^2)
	空间复杂度：O(1)
	稳定性：稳定
	基本思想：通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应的位置并插入
		1.从元素的第一个位置开始（0这个位置视为已排好的有序序列），将key=arr[j]
		2.将key与其前面的有序序列进行对比，看是否向后移动序列
		3.找到合适的位置将其插入
'''
from tool import arr
def InsertSort(arr):
	if arr == None or len(arr) == 0:
		return 0
	j = 1
	while j < len(arr):
		i = j - 1
		key = arr[j]
		while i >= 0 and arr[i] > key:
			# 元素向后移动
			arr[i + 1] = arr[i]
			i = i - 1
		# 将key插入到合适的位置
		arr[i + 1] = key
		j = j + 1
	return arr

if __name__ == '__main__':
	arr = InsertSort(arr)
	print(arr)